package Yesterday;

public class Solution1 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    //给出前序遍历 和 中序遍历 来构建二叉树
    //以前序遍历的方式构建 中序遍历辅助分出左右子树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0, preorder.length);
    }
    /*需要的数据有：一个结点来遍历先序序列的数组 这个结点不能是局部变量 得是成员变量
                 需要Begin 和 End 结点 包含的的范围是中序遍历查找的范围
                 先序：根 左 右 -- 遍历到根的时候 在中序遍历中找到根节点对应的下标 分为左右子树
                 定义一个局部变量来存储下标 以他为基础来对范围进行修改
     */
    public int prestep;  //先序遍历进行到哪一步
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int begin,int end) {
        if(begin > end) {
            return null;
        }
        TreeNode cur = new TreeNode(preorder[prestep]);
        int instep = findTree(inorder,begin,end,preorder[prestep]);
        prestep++;
        cur.left = buildTreeChild(preorder,inorder,begin,instep-1);
        cur.right = buildTreeChild(preorder,inorder,instep+1,end);
        return cur;
    }
    public int findTree(int[] inorder,int begin,int end,int key) {
        for (int i = begin; i <= end; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}